#include <iostream>
#include <cstring>
using namespace std;
#define maxn 64
#define maxv 320001

int totalPrice, n;
int v[maxn], w[maxn], slave[maxn][2];
bool isSlave[maxn];
int dp[maxn][maxv];

int dfs(int i, int cprice){
	if(dp[i][cprice]>=0) return dp[i][cprice];
	if(i>n) return 0;
	if(isSlave[i]) return dfs(i+1, cprice);
	int ans0=0, ans1=0, ans2=0, ans3=0, ans4=0;
	
	ans0 = dfs(i+1, cprice);
	if(cprice+v[i] <= totalPrice)
		ans1 = dfs(i+1, cprice+v[i])+v[i]*w[i];
	if(cprice+v[i]+v[slave[i][0]] <= totalPrice)
		ans2 = dfs(i+1, cprice+v[i]+v[slave[i][0]]) \
			+ v[i]*w[i]+v[slave[i][0]]*w[slave[i][0]];
	if(cprice+v[i]+v[slave[i][1]] <= totalPrice)
		ans3 = dfs(i+1, cprice+v[i]+v[slave[i][1]]) \
			+ v[i]*w[i]+v[slave[i][1]]*w[slave[i][1]];
	if(cprice+v[i]+v[slave[i][0]]+v[slave[i][1]] <= totalPrice)
		ans4 = dfs(i+1, cprice+v[i]+v[slave[i][0]]+v[slave[i][1]]) \
			+ v[i]*w[i]+v[slave[i][0]]*w[slave[i][0]]+v[slave[i][1]]*w[slave[i][1]];
	
	return dp[i][cprice] = max(ans0, max(ans1, max(ans2, max(ans3, ans4))));
}

int main(){
	memset(dp, -1, sizeof(dp));
	cin>>totalPrice>>n;
	for(int i=1; i<=n; i++){
		int slaved;
		cin>>v[i]>>w[i]>>slaved;
		if(slaved!=0) isSlave[i]=true;
		if(slave[slaved][0]==0)
			slave[slaved][0]=i;
		else
			slave[slaved][1]=i;
	}
	
	cout<<dfs(1, 0)<<endl;

	return 0;
}